/***
 * * PROJECT
 * *    Logical Neighborhood Routing
 * * VERSION
 * *    $Revision: 1.7 $
 * * DATE
 * *    $Date: 2007/06/01 20:52:31 $
 * * LOG
 * *    $Log: LNSimpleEstimator.java,v $
 * *    Revision 1.7  2007/06/01 20:52:31  animesh
 * *    bulk update.
 * *
 * *    Revision 1.6  2007/02/02 11:23:59  lmottola
 * *    Benchmarking code for compiler in.
 * *
 * *    Revision 1.5  2007/01/29 17:48:01  lmottola
 * *    Added debug info in toString() method.
 * *
 * *    Revision 1.4  2007/01/10 22:57:04  lmottola
 * *    LNStaticHelper added.
 * *
 * *    Revision 1.3  2007/01/04 09:22:42  lmottola
 * *    Changed getEstimation signature in Estimator interface.
 * *
 * *    Revision 1.2  2006/12/20 23:05:50  lmottola
 * *    SWANS-based simulator in.
 * *
 * *    Revision 1.1  2006/12/15 06:48:35  lmottola
 * *    First version of LNEstimator in.
 * *
 * *    Revision 1.1  2006/12/14 18:59:59  lmottola
 * *    Modified Estimator interface.
 * *
 * *
 * *   Logical Neighborhoods Routing - Java Version
 * *
 * *   This program is free software; you can redistribute it and/or
 * *   modify it under the terms of the GNU General Public License
 * *   as published by the Free Software Foundation; either version 2
 * *   of the License, or (at your option) any later version.
 * *
 * *   This program is distributed in the hope that it will be useful,
 * *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 * *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * *   GNU General Public License for more details.
 * *
 * *   You should have received a copy of the GNU General Public License
 * *   along with this program; if not, you may find a copy at the FSF web
 * *   site at 'www.gnu.org' or 'www.fsf.org', or you may write to the
 * *   Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * *   Boston, MA  02111-1307, USA
 ***/

package atag.runtime.ln.estimation;

import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

import atag.common.NetworkTopology;
import atag.compiler.CommPattern;
import atag.compiler.Estimator;
import atag.runtime.NodeInfo;
import atag.runtime.ln.estimation.mst.Graph;
import atag.runtime.ln.nodeAttributes.NodeAttribute;

/**
 * This class implements a very simply approximation of the LN routing protocol.
 * It assumes all transmissions are perfectly reliable, and all probabilistic
 * choices are immediately the "right" ones. As such it represents an ideal
 * solution that only approximates the actual protocol's behavior.
 *
 * @author Luca Mottola <a
 *         href="mailto:mottola@elet.polimi.it">mottola@elet.polimi.it</a>
 *
 */
public class LNSimpleEstimator implements Estimator {
    
    private HashMap<Integer, GraphNode> graphNodes;
    
    private NetworkTopology topology;
    
    private Graph graph;
    
    private final static int EDGE_COST = 1;
    
    private final static int MSG_COST = 1;
    
    // TODO: Add support for max hops in scopes, and overlapping paths
    
    public LNSimpleEstimator(NetworkTopology topology) {
        
        this.topology = topology;
        this.graphNodes = new HashMap<Integer, GraphNode>();
        LinkedList<NodeInfo> nodes = new LinkedList<NodeInfo>(topology.getNodes());
        
        // Building the graph
        graph = new Graph();
        Iterator<NodeInfo> it = nodes.iterator();
        while (it.hasNext()) {
            NodeInfo node = it.next();
            graphNodes.put(node.getMyId(), new GraphNode(node.getMyId()));
            graph.addEdge(String.valueOf(node.getMyId()), 
                    String.valueOf(node.getMyId()), 0);
            Iterator<NodeInfo> itNgh = topology.getNeighborsOf(node.getMyId())
            .iterator();
            while (itNgh.hasNext()) {
                NodeInfo ngh = itNgh.next();
                // System.out.println("Creating edge from " + node.getMyId()
                // + " to " + ngh.getMyId());
                graph.addEdge(String.valueOf(node.getMyId()), String.valueOf(ngh
                        .getMyId()), EDGE_COST);
            }
        }
        
        // Computing the all to all shortest path
        // System.out.println("Computing all to all shortest paths");
        it = nodes.iterator();
        while (it.hasNext()) {
            NodeInfo root = it.next();
            // System.out.println("Taking " + root.getMyId() + " as root");
            graph.dijkstra(String.valueOf(root.getMyId()));
            
            Iterator<NodeInfo> itStoreSP = nodes.iterator();
            while (itStoreSP.hasNext()) {
                NodeInfo nodeSP = itStoreSP.next();
                int nodeSPpred;
                // Fix needed as the algorithm does not set the precedessor for
                // the root itself
                if (nodeSP.getMyId() != root.getMyId()) {
                    nodeSPpred = Integer.valueOf(graph.getVertex(
                            String.valueOf(nodeSP.getMyId())).getPredecessorName());
                } else {
                    nodeSPpred = root.getMyId();
                }
                // System.out.println("For root " + root.getMyId()
                // + ", the pred of " + nodeSP.getMyId() + " is "
                // + nodeSPpred);
                graphNodes.get(nodeSP.getMyId()).setPredecessorTo(root.getMyId(),
                        nodeSPpred);
            }
        }
        
        // Determining the state space profile
        it = nodes.iterator();
        while (it.hasNext()) {
            NodeInfo node = it.next();
            Iterator<NodeAttribute> attrIt = node.getNodeAttributes().iterator();
            while (attrIt.hasNext()) {
                NodeAttribute attr = attrIt.next();
                Iterator<NodeInfo> sourceIt = nodes.iterator();
                while (sourceIt.hasNext()) {
                    GraphNode source = graphNodes.get(sourceIt.next().getMyId());
                    source.addNextHopForAttr(attr, source
                            .getPredecessorTo(node.getMyId()));
                }
            }
        }
    }
    
    public double[] getCostEstimate(List commPatterns) {
        
        // FIXME: (Luca) The value returned is the number of generated messages,
        // we need something more flexibile/expressive, not just a double value
        // FIXED - Luca changed it to a double[]
        
        int cost = 0;
        double[] nodeCosts = new double[topology.getNumberOfNodes()];
        
        for (int i = 0; i < nodeCosts.length; i++) {
            nodeCosts[i] = 0;
        }
        
        boolean debug = false; //Animesh - change this as needed. controls prints
        
        
        // Computing the communication costs
        Iterator<? extends CommPattern> itPatterns = commPatterns.iterator();
        while (itPatterns.hasNext()) {
            CommPattern commPatt = itPatterns.next();
            LinkedList<Integer> matchingNodes = LNStaticHelper
                    .determineMatchingNodes(topology, commPatt.getCommScope());
            if(debug){
                System.out.println(commPatt.getCommScope().toString());
                System.out.println(topology.toString());
                System.out.println("matchingNodes " + matchingNodes.size() + "\n");
            }
            Iterator<Integer> itNodes = matchingNodes.iterator();
            while (itNodes.hasNext()) {
                GraphNode receiver = graphNodes.get(itNodes.next());
                cost += evaluatePath(graphNodes.get(commPatt.getNodeId()), receiver);
                processPath(graphNodes.get(commPatt.getNodeId()), receiver, nodeCosts);
            }
        }
        return nodeCosts;
    }
    
    private void processPath(GraphNode source, GraphNode receiver, double[] nodeCosts) {
        
        if (source.getId() != receiver.getId()) {
            nodeCosts[receiver.getPredecessorTo(source.getId())]++;
            processPath(source, graphNodes.get(receiver.getPredecessorTo(source
                    .getId())), nodeCosts);
        }
    }
    
    private int evaluatePath(GraphNode source, GraphNode receiver) {
        
        if (source.getId() == receiver.getId()) {
            return 0;
        } else {
            return MSG_COST
                    + evaluatePath(source, graphNodes.get(receiver
                    .getPredecessorTo(source.getId())));
        }
    }
    
    class GraphNode {
        
        private int id;
        
        private HashMap<Integer, Integer> precedecessors;
        
        private HashMap<NodeAttribute, LinkedList<Integer>> nextHopAttributes;
        
        public GraphNode(int id) {
            this.id = id;
            this.precedecessors = new HashMap<Integer, Integer>();
            this.nextHopAttributes = new HashMap<NodeAttribute, LinkedList<Integer>>();
        }
        
        public int getPredecessorTo(int rootId) {
            return precedecessors.get(rootId);
        }
        
        public void setPredecessorTo(int rootId, int predId) {
            precedecessors.put(rootId, predId);
        }
        
        public void addNextHopForAttr(NodeAttribute attr, int nextHop) {
            LinkedList<Integer> nextHops = nextHopAttributes.get(attr);
            if (nextHops == null) {
                nextHops = new LinkedList<Integer>();
                nextHopAttributes.put(attr, nextHops);
            }
            nextHops.add(nextHop);
        }
        
        public int getId() {
            return id;
        }
    }
}
